{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Chocolate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximizeSweetness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分享巧克力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组&nbsp;<code>sweetness</code>&nbsp;来表示每一小块的甜度。</p>\n",
    "\n",
    "<p>你打算和&nbsp;<code>K</code>&nbsp;名朋友一起分享这块巧克力，所以你需要将切割&nbsp;<code>K</code>&nbsp;次才能得到 <code>K+1</code>&nbsp;块，每一块都由一些 <strong>连续&nbsp;</strong>的小块组成。</p>\n",
    "\n",
    "<p>为了表现出你的慷慨，你将会吃掉&nbsp;<strong>总甜度最小</strong> 的一块，并将其余几块分给你的朋友们。</p>\n",
    "\n",
    "<p>请找出一个最佳的切割策略，使得你所分得的巧克力&nbsp;<strong>总甜度最大</strong>，并返回这个 <strong>最大总甜度</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>sweetness = [1,2,3,4,5,6,7,8,9], K = 5\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>sweetness = [5,6,7,8,9,1,2,3,4], K = 8\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只有一种办法可以把巧克力分成 9 块。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>sweetness = [1,2,2,1,2,2,1,2,2], K = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= K &lt;&nbsp;sweetness.length &lt;= 10^4</code></li>\n",
    "\t<li><code>1 &lt;= sweetness[i] &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-chocolate](https://leetcode.cn/problems/divide-chocolate/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-chocolate](https://leetcode.cn/problems/divide-chocolate/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8,9]\\n5', '[5,6,7,8,9,1,2,3,4]\\n8', '[1,2,2,1,2,2,1,2,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        n = len(sweetness)\n",
    "        if k == n-1:\n",
    "            return min(sweetness)\n",
    "        left, right = min(sweetness), sum(sweetness)//(k+1)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1)//2\n",
    "            cur_sweet = 0\n",
    "            count = 0\n",
    "            for num in sweetness:\n",
    "                cur_sweet += num\n",
    "                if cur_sweet >= mid:\n",
    "                    count += 1\n",
    "                    cur_sweet = 0\n",
    "            \n",
    "            if count >= k+1:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        num_people = k + 1\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness) // num_people\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            cur_sweetness = 0\n",
    "            people_with_chocolate = 0\n",
    "            for s in sweetness:\n",
    "                cur_sweetness += s\n",
    "\n",
    "                if cur_sweetness >= mid:\n",
    "                    people_with_chocolate += 1\n",
    "                    cur_sweetness = 0\n",
    "            if people_with_chocolate >= num_people:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        n = k + 1\n",
    "\n",
    "        left, right = min(sweetness), sum(sweetness) // n\n",
    "        while left < right:\n",
    "            middle = (left + right + 1) // 2\n",
    "            \n",
    "            currSweetnss = 0\n",
    "            people = 0\n",
    "            for s in sweetness:\n",
    "                currSweetnss += s\n",
    "                if currSweetnss >= middle:\n",
    "                    people += 1\n",
    "                    currSweetnss = 0\n",
    "            if people >= n:\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        number_of_people = k + 1\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness) // number_of_people\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) //2\n",
    "            cur_sweetness = 0\n",
    "            people_with_chocolate = 0\n",
    "\n",
    "            for s in sweetness:\n",
    "                cur_sweetness += s\n",
    "\n",
    "                if cur_sweetness >= mid:\n",
    "                    people_with_chocolate += 1\n",
    "                    cur_sweetness = 0\n",
    "            \n",
    "            if people_with_chocolate >= k + 1:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: [int], k: int) -> int:\n",
    "        if k + 1 == len(sweetness):\n",
    "            return min(sweetness)\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness) // (k + 1)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            allocated = 0\n",
    "            allocated_sum = 0\n",
    "            for candy in sweetness:\n",
    "                allocated_sum += candy\n",
    "                if allocated_sum >= mid:\n",
    "                    allocated += 1\n",
    "                    allocated_sum = 0\n",
    "            if allocated >= k + 1:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l,r = min(sweetness),sum(sweetness)//(k+1)\n",
    "        while l<r:\n",
    "            mid = (l+r+1)//2\n",
    "            if self.isEligible(sweetness,k,mid):\n",
    "                l= mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l\n",
    "    \n",
    "    def isEligible(self, sweetness:List[int],k:int,mine: int) -> bool:\n",
    "        if len(sweetness) < k:\n",
    "            return False\n",
    "        \n",
    "        tot,cnt =0,0\n",
    "        for s in sweetness:\n",
    "            tot += s\n",
    "\n",
    "            if tot >= mine:\n",
    "                tot =0\n",
    "                cnt += 1\n",
    "            \n",
    "        if cnt >k:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def checksweet(nums, upper, k):\n",
    "            count = 0\n",
    "            agg = 0\n",
    "            for num in nums:\n",
    "                agg += num\n",
    "                if agg >= upper:\n",
    "                    agg = 0\n",
    "                    count  += 1\n",
    "            return count >= k + 1\n",
    "\n",
    "        minSweet = min(sweetness)\n",
    "        maxSweet = sum(sweetness)\n",
    "        while minSweet < maxSweet:\n",
    "            mid = (minSweet + maxSweet + 1) // 2\n",
    "            if checksweet(sweetness, mid, k):                \n",
    "                minSweet = mid\n",
    "            else:\n",
    "                maxSweet = mid - 1\n",
    "        return minSweet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check_feasible(minSweet):\n",
    "            acc_sum = 0\n",
    "            count = 0\n",
    "            for i in range(len(sweetness)):\n",
    "                acc_sum += sweetness[i]\n",
    "                if acc_sum >= minSweet:\n",
    "                    acc_sum = 0\n",
    "                    count += 1\n",
    "            return count >= (k + 1)\n",
    "        \n",
    "        summ = sum(sweetness)\n",
    "        aveSweet = summ // (k + 1)\n",
    "        left = 0\n",
    "        right = aveSweet\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check_feasible(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        \n",
    "        def check(x):\n",
    "            cnt = pre = 0\n",
    "            for num in sweetness:\n",
    "                pre += num\n",
    "                if pre >= x:\n",
    "                    cnt += 1\n",
    "                    pre = 0\n",
    "            return cnt >= k+1\n",
    "        \n",
    "        return BinarySearch().find_int_right(0, sum(sweetness), check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], K: int) -> int:\n",
    "        def check(x):\n",
    "            s = 0\n",
    "            count = 0\n",
    "            for num in sweetness:\n",
    "                s += num\n",
    "                if s >= x:\n",
    "                    count += 1\n",
    "                    s = 0\n",
    "            return count >= K + 1\n",
    "\n",
    "        l, r = 0, sum(sweetness) // (K + 1)\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        # 二分法\n",
    "        # 很棒的解法：\n",
    "        # https://leetcode.cn/problems/divide-chocolate/solutions/1328110/by-jiong-jiong-jiong-jiong-z-p2wx/?envType=study-plan-v2&envId=baidu-2023-fall-sprint\n",
    "        def check_feasible(minSweet):\n",
    "            acc_sum = 0\n",
    "            count = 0\n",
    "            for i in range(len(sweetness)):\n",
    "                acc_sum += sweetness[i]\n",
    "                if acc_sum >= minSweet:\n",
    "                    acc_sum = 0\n",
    "                    count += 1\n",
    "            return count >= (k + 1)\n",
    "        \n",
    "        summ = sum(sweetness)\n",
    "        aveSweet = summ // (k + 1)\n",
    "        left = 0\n",
    "        right = aveSweet\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check_feasible(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        n = len(sweetness)\n",
    "        prefix = [0]\n",
    "        for i in range(n):\n",
    "            prefix.append(sweetness[i] + prefix[i])\n",
    "\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            nxt = x\n",
    "            while nxt <= prefix[-1]:\n",
    "                idx = bisect_left(prefix, nxt)\n",
    "                if idx >= n + 1:\n",
    "                    break\n",
    "                nxt = prefix[idx] + x\n",
    "                cnt += 1\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        # o(nlogn + nlogc) c是最大值\n",
    "        l, r = 0, sum(sweetness) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l = len(sweetness)\n",
    "        \n",
    "        mini = min(sweetness)\n",
    "        maxi = sum(sweetness)//(k+1)+1\n",
    "        mid = mini\n",
    "\n",
    "        while maxi>mini:\n",
    "            if mid == (mini+maxi)//2:\n",
    "                return mid\n",
    "            mid = (mini+maxi)//2\n",
    "            s = 0\n",
    "            p = k+1\n",
    "            for c in sweetness:\n",
    "                s += c\n",
    "                if s >= mid:\n",
    "                    s = 0\n",
    "                    p -= 1\n",
    "                if p==0:\n",
    "                    break\n",
    "            \n",
    "            if p == 0:\n",
    "                mini = mid\n",
    "            else:\n",
    "                maxi = mid\n",
    "            print(mini, maxi)\n",
    "            \n",
    "        return mid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "\n",
    "        def check(minSize):\n",
    "            cnt, cur_swt = 0, 0\n",
    "\n",
    "            for sweet in sweetness:\n",
    "                cur_swt += sweet\n",
    "                if cur_swt >= minSize:\n",
    "                    cur_swt = 0\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        low, high = min(sweetness), sum(sweetness) // (k + 1) + 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid) < k + 1:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return low - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            tmp = 0\n",
    "            for v in sweetness:\n",
    "                tmp += v\n",
    "                if tmp >= x:\n",
    "                    tmp = 0\n",
    "                    cnt += 1\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        # o(nlogn + nlogc) c是最大值\n",
    "        l, r = 0, sum(sweetness) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: [int], k: int) -> int:\n",
    "        if k + 1 == len(sweetness):\n",
    "            return min(sweetness)\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness) // (k + 1)\n",
    "        res = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            allocated = 0\n",
    "            allocated_sum = 0\n",
    "            for candy in sweetness:\n",
    "                allocated_sum += candy\n",
    "                if allocated_sum >= mid:\n",
    "                    allocated += 1\n",
    "                    allocated_sum = 0\n",
    "            if allocated >= k + 1:\n",
    "                left = mid + 1\n",
    "                res = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        n = len(sweetness)\n",
    "        prefix = [0]\n",
    "        for v in sweetness:\n",
    "            prefix.append(v + prefix[-1])\n",
    "\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            nxt = x\n",
    "            while nxt <= prefix[-1]:\n",
    "                idx = bisect_left(prefix, nxt)\n",
    "                if idx >= n + 1:\n",
    "                    break\n",
    "                nxt = prefix[idx] + x\n",
    "                cnt += 1\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        # o(nlogn + nlogc) c是最大值\n",
    "        l, r = 0, sum(sweetness) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        # def dfs(sweetness,res,k,target,i):\n",
    "        #     if k==0:\n",
    "        #         tmp=res\n",
    "        #         res=min(sum(sweetness[i+1:]),res)\n",
    "        #         if res>=target:\n",
    "        #             res=tmp\n",
    "        #             return True\n",
    "        #         res=tmp\n",
    "        #         return False\n",
    "        #     if len(sweetness)-1-i<k+1:\n",
    "        #         return False\n",
    "        #     tmp=res\n",
    "        #     for j in range(i+1,len(sweetness)-1):\n",
    "        #         res=min(sum(sweetness[i+1:j+1]),res)\n",
    "        #         if res<target:\n",
    "        #             res=tmp\n",
    "        #             continue\n",
    "        #         if dfs(sweetness,res,k-1,target,j):\n",
    "        #             res=tmp\n",
    "        #             return True\n",
    "        def check(limit):\n",
    "            cnt = 0\n",
    "            pre = 0\n",
    "            for num in sweetness:\n",
    "                pre += num\n",
    "                if pre >= limit:\n",
    "                    cnt += 1\n",
    "                    pre = 0\n",
    "                    if cnt >= k+1:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        if k==0:\n",
    "            return sum(sweetness)\n",
    "        if k==len(sweetness)-1:\n",
    "            return min(sweetness)\n",
    "        \n",
    "        left,right=min(sweetness),sum(sweetness)\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(n):\n",
    "            cnt = s = 0\n",
    "            for x in sweetness:\n",
    "                s += x\n",
    "                if s >= n:\n",
    "                    cnt += 1\n",
    "                    s = 0\n",
    "            return cnt >= k + 1\n",
    "\n",
    "\n",
    "        left, right = min(sweetness), sum(sweetness) // (k+1)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        avg = sum(sweetness) // (k+1)\n",
    "        l = 0\n",
    "        r = avg\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if self.isfeasiable(mid, sweetness, k):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "    def isfeasiable(self, val: int, sweetness: List[int], k: int) -> bool:\n",
    "        temp = 0\n",
    "        count = 0\n",
    "        for v in sweetness:\n",
    "            temp += v\n",
    "            if temp >= val:\n",
    "                count += 1\n",
    "                temp = 0\n",
    "        return count > k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(n):\n",
    "            cnt = s = 0\n",
    "            for x in sweetness:\n",
    "                s += x\n",
    "                if s >= n:\n",
    "                    cnt += 1\n",
    "                    s = 0\n",
    "            return cnt >= k + 1\n",
    "\n",
    "\n",
    "        left, right = 0, sum(sweetness) // (k+1)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], K: int) -> int:\n",
    "        l, r = min(sweetness) - 1, sum(sweetness) + 1\n",
    "        while l + 1 != r:\n",
    "            mid = (l + r) // 2\n",
    "            k = 0\n",
    "            c = 0\n",
    "            for sw in sweetness:\n",
    "                c += sw \n",
    "                if c >= mid:\n",
    "                    c = 0 \n",
    "                    k += 1\n",
    "            if k >= K + 1:\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l = len(sweetness)\n",
    "        \n",
    "        mini = min(sweetness)\n",
    "        maxi = sum(sweetness)//(k+1)+1\n",
    "        mid = mini\n",
    "\n",
    "        while maxi>mini:\n",
    "            if mid == (mini+maxi)//2:\n",
    "                return mid\n",
    "            mid = (mini+maxi)//2\n",
    "            s = 0\n",
    "            p = k+1\n",
    "            for c in sweetness:\n",
    "                s += c\n",
    "                if s >= mid:\n",
    "                    s = 0\n",
    "                    p -= 1\n",
    "                if p==0:\n",
    "                    break\n",
    "            \n",
    "            if p == 0:\n",
    "                mini = mid\n",
    "            else:\n",
    "                maxi = mid\n",
    "            # print(mini, maxi)\n",
    "            \n",
    "        return mid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(n):\n",
    "            cnt = s = 0\n",
    "            for x in sweetness:\n",
    "                s += x\n",
    "                if s >= n:\n",
    "                    cnt += 1\n",
    "                    s = 0\n",
    "            return cnt >= k + 1\n",
    "\n",
    "\n",
    "        left, right = min(sweetness), sum(sweetness) // (k+1)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        left, right = min(sweetness), sum(sweetness) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            cur, cnt = 0, 0\n",
    "            for i in sweetness:\n",
    "                cur += i\n",
    "                if cur >= mid:\n",
    "                    cur = 0\n",
    "                    cnt += 1\n",
    "\n",
    "            if cnt >= k + 1:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def isFeasible(minSweetness, sweetness, k):\n",
    "            nsum, count = 0, 0\n",
    "            for sweet in sweetness:\n",
    "                nsum += sweet\n",
    "                if nsum >= minSweetness:\n",
    "                    count += 1\n",
    "                    nsum = 0\n",
    "            return count >= k + 1\n",
    "\n",
    "        avg_sweetness = sum(sweetness) // (k + 1)\n",
    "        l, r = 0, avg_sweetness\n",
    "        while l <= r:\n",
    "            mid = l + ((r - l) >> 1)\n",
    "            if isFeasible(mid, sweetness, k):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        number_of_people = k+1\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness)//number_of_people\n",
    "        while(left<right):\n",
    "            mid = left+(right-left+1)//2\n",
    "            cur_s = 0\n",
    "            people = 0\n",
    "            for i in sweetness:\n",
    "                cur_s += i\n",
    "                if cur_s>=mid:\n",
    "                    people+=1\n",
    "                    cur_s = 0\n",
    "            if people>=number_of_people:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(mid):\n",
    "            # mid: split based on mid\n",
    "            count = 0\n",
    "            temp = 0\n",
    "            for num in sweetness:\n",
    "                temp += num\n",
    "                if temp >= mid:\n",
    "                    count += 1\n",
    "                    temp = 0\n",
    "            return count >= k+1\n",
    "        \n",
    "        left = 0\n",
    "        right = sum(sweetness)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(x):\n",
    "            s=0\n",
    "            count =0\n",
    "            for num in sweetness :\n",
    "                s+=num\n",
    "                if s>=x:\n",
    "                    count +=1\n",
    "                    s=0\n",
    "            return count >=k+1\n",
    "        l,r=0,sum(sweetness)//(k+1)\n",
    "        while l<r:\n",
    "            mid=l+(r-l+1)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        # 初始化左右边界。\n",
    "        # left = 1 and right = (total sweetness) / (number of people).\n",
    "        number_of_people = k + 1\n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness) // number_of_people\n",
    "        \n",
    "        while left < right:\n",
    "            # 获取左右边界之前的中间值索引。\n",
    "            # cur_sweetness 表示当前人的总甜度。\n",
    "            # people_with_chocolate 表示有一块巧克力甜度大于等于 mid 的人数。\n",
    "            mid = (left + right + 1) // 2\n",
    "            cur_sweetness = 0\n",
    "            people_with_chocolate = 0\n",
    "            \n",
    "            # 开始为当前人分配块。\n",
    "            for s in sweetness:\n",
    "                cur_sweetness += s\n",
    "                \n",
    "                # 如果总甜度不小于 mid，意味着我们可以掰开当前块并且继续为下一个人分配。\n",
    "                if cur_sweetness >= mid:\n",
    "                    people_with_chocolate += 1\n",
    "                    cur_sweetness = 0\n",
    "\n",
    "            if people_with_chocolate >= k + 1:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def can_split(min_total):\n",
    "            count = 0\n",
    "            total = 0\n",
    "\n",
    "            for s in sweetness:\n",
    "                total += s\n",
    "                if total >= min_total:\n",
    "                    total = 0 # 从下一个开始新数组，保证每个数组的和都>=min_total\n",
    "                    count += 1 # 多分了一份\n",
    "\n",
    "            return count >= n\n",
    "\n",
    "        n = k + 1 # 分成 k + 1 份\n",
    "        left, right = min(sweetness), sum(sweetness) // n\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if can_split(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        # 按照甜度二分\n",
    "        def check(n):\n",
    "            cnt = total = 0\n",
    "            for x in sweetness:\n",
    "                total += x\n",
    "                if total >= n:\n",
    "                    cnt += 1\n",
    "                    total = 0\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        start, end = min(sweetness), sum(sweetness)\n",
    "        while start <= end:\n",
    "            mid = (start + end) >> 1\n",
    "            if check(mid):\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "        return end "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "#         def count(minval):\n",
    "#             theSum = 0\n",
    "#             count = 0\n",
    "\n",
    "#             for each in range(sweetness):\n",
    "#                 if theSum + each >= minval:\n",
    "#                     theSum = 0\n",
    "#                     count += 1\n",
    "#                 else:\n",
    "#                     theSum += each\n",
    "            \n",
    "#             return count\n",
    "        \n",
    "#         # \n",
    "#         index = bisect_left(min(sweetness), sum(sweetness)+1, key = count)\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, nums: List[int], k: int) -> int:\n",
    "        def count(minimal):\n",
    "            count,total=0,0\n",
    "            for i in nums:\n",
    "                if i+total>=minimal:\n",
    "                    count+=1\n",
    "                    total=0\n",
    "                else:\n",
    "                    total+=i\n",
    "            return count\n",
    "        index=bisect_left(range(sum(nums),min(nums)-1,-1), k+1, key=count)\n",
    "        return sum(nums)-index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return sum(sweetness)\n",
    "\n",
    "        l = min(sweetness)\n",
    "        r = sum(sweetness) // (k + 1)\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            count = 0\n",
    "            s = 0\n",
    "            for sweet in sweetness:\n",
    "                s += sweet\n",
    "                if s >= mid:\n",
    "                    count += 1\n",
    "                    s = 0\n",
    "            if s >= mid:\n",
    "                count += 1\n",
    "\n",
    "            if count < k + 1:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        cumsum = [0]*(len(sweetness)+1)\n",
    "        for i in range(1, len(sweetness)+1):\n",
    "            cumsum[i] += cumsum[i-1] + sweetness[i-1]\n",
    "        def available(m: int, k: int) -> bool:\n",
    "            last, times = 0, 0\n",
    "            for i, item in enumerate(cumsum):\n",
    "                if item - cumsum[last] >= m:\n",
    "                    times += 1\n",
    "                    last = i\n",
    "            return times >= k+1\n",
    "\n",
    "        i, j = 1, cumsum[-1]//(k+1)\n",
    "        valid = 0\n",
    "        while i <= j:\n",
    "            m = (i+j)//2\n",
    "            if available(m, k):\n",
    "                valid = m\n",
    "                i = m+1\n",
    "            else:\n",
    "                j = m-1\n",
    "        return valid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        n = len(sweetness)\n",
    "        prefix = [0]\n",
    "        for v in sweetness:\n",
    "            prefix.append(v + prefix[-1])\n",
    "\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            nxt = x\n",
    "            i, j = 0, n + 1\n",
    "            while nxt <= prefix[-1] and i < n + 1:\n",
    "                i = bisect_left(prefix, nxt, i + 1, j)\n",
    "                if i >= n + 1:\n",
    "                    break\n",
    "                nxt = prefix[i] + x\n",
    "                cnt += 1\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        # o(nlogn + nlogc) c是最大值\n",
    "        l, r = 0, sum(sweetness) + 1\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(x):\n",
    "            cut = 0\n",
    "            sumup = 0\n",
    "            for i in sweetness:\n",
    "                sumup+=i\n",
    "                if sumup>x:\n",
    "                    sumup=0\n",
    "                    cut+=1\n",
    "            return cut<=k\n",
    "\n",
    "        left,right = min(sweetness),sum(sweetness)\n",
    "        while(left<right):\n",
    "            mid = left + (right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l = len(sweetness)\n",
    "        \n",
    "        mini = min(sweetness)\n",
    "        maxi = sum(sweetness)//(k+1)+1\n",
    "        mid = mini\n",
    "\n",
    "        while maxi>mini:\n",
    "\n",
    "            mid = (mini+maxi+1)//2\n",
    "            s = 0\n",
    "            p = k+1\n",
    "            for c in sweetness:\n",
    "                s += c\n",
    "                if s >= mid:\n",
    "                    s = 0\n",
    "                    p -= 1\n",
    "                if p==0:\n",
    "                    break\n",
    "            \n",
    "            if p == 0:\n",
    "                mini = mid\n",
    "            else:\n",
    "                maxi = mid-1\n",
    "            # print(mini, maxi)\n",
    "            \n",
    "        return maxi\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        s = sum(sweetness)\n",
    "        if k == 0: return s\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            s = 0\n",
    "            for x in sweetness:\n",
    "                s += x\n",
    "                if s >= mid:\n",
    "                    s = 0\n",
    "                    cnt += 1\n",
    "            return cnt >= k + 1\n",
    "\n",
    "        l, r = min(sweetness), s\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        '''\n",
    "        竟然是用二分来解决，但确实时间复杂度较低，算是某种思维盲区了，以后要注意\n",
    "        '''\n",
    "        if k == 0:\n",
    "            return sum(sweetness)\n",
    "\n",
    "        l = min(sweetness)\n",
    "        r = sum(sweetness) // (k + 1)\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            count = 0\n",
    "            s = 0\n",
    "            for sweet in sweetness:\n",
    "                s += sweet\n",
    "                if s >= mid:\n",
    "                    count += 1\n",
    "                    s = 0\n",
    "            if s >= mid:\n",
    "                count += 1\n",
    "\n",
    "            if count < k + 1:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l, r = min(sweetness), sum(sweetness) // (k + 1)\n",
    "        mid = (l + r) // 2 + 1\n",
    "        while l < r:\n",
    "            x, tmp = 0, 0\n",
    "            for emp in sweetness:\n",
    "                tmp += emp\n",
    "                if tmp >= mid:\n",
    "                    x += 1\n",
    "                    tmp = 0\n",
    "            if x >= k + 1:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "            mid = (l + r) // 2 + 1\n",
    "        print(l)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            s = cnt = 0\n",
    "            for v in sweetness:\n",
    "                s += v\n",
    "                if s >= x:\n",
    "                    s = 0\n",
    "                    cnt += 1\n",
    "            return cnt > k\n",
    "        \n",
    "        l, r = 0, sum(sweetness)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二分法\n",
    "# 下限：所有甜度的最小值\n",
    "# 上限：所有甜度的均值\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def check(mid):\n",
    "            s_cnt, k_cnt = 0, 0\n",
    "            for sweet in sweetness:\n",
    "                s_cnt += sweet\n",
    "                if s_cnt >= mid:\n",
    "                    k_cnt += 1\n",
    "                    s_cnt = 0\n",
    "            return k_cnt > k\n",
    "\n",
    "        left, right = min(sweetness), sum(sweetness) // (k + 1)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximizeSweetness(self, sweetness, k):\n",
    "        def feasible(min_sum_sw):\n",
    "            n = 0\n",
    "            sum = 0\n",
    "            for sw in sweetness:\n",
    "                sum += sw\n",
    "                if sum >= min_sum_sw:\n",
    "                    sum = 0\n",
    "                    n += 1\n",
    "            return n >= k + 1\n",
    "\n",
    "        l, r = 1, sum(sweetness) // (k + 1)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if not feasible(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def get_piece(sweet_value):\n",
    "            count = 0\n",
    "            val = 0\n",
    "            for num in sweetness:\n",
    "                val += num\n",
    "                if val >= sweet_value:\n",
    "                    val = 0\n",
    "                    count += 1\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        left = min(sweetness)\n",
    "        right = sum(sweetness)\n",
    "        \n",
    "        mid = 0\n",
    "        k += 1\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            mid2 = left + (right - left) // 2\n",
    "            count = get_piece(mid)\n",
    "            if count >= k :\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        \n",
    "        return max(min(sweetness), right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def getPieces(ref):\n",
    "            count = 0\n",
    "            sum = 0\n",
    "            for num in sweetness:\n",
    "                sum += num\n",
    "                if sum >= ref:\n",
    "                    count += 1\n",
    "                    sum = 0\n",
    "            return count\n",
    "        minSweet = min(sweetness)\n",
    "        left = minSweet\n",
    "        right = sum(sweetness)\n",
    "        mid = 0\n",
    "        midVal = 0\n",
    "        k += 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            midVal = getPieces(mid)\n",
    "            if midVal >= k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return max(minSweet, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        l = len(sweetness)\n",
    "        \n",
    "        mini = min(sweetness)\n",
    "        maxi = sum(sweetness)//(k+1)+1\n",
    "        mid = mini\n",
    "\n",
    "        while maxi>mini:\n",
    "            if mid == (mini+maxi)//2:\n",
    "                return mid\n",
    "            mid = (mini+maxi)//2\n",
    "            s = 0\n",
    "            p = k+1\n",
    "            for c in sweetness:\n",
    "                s += c\n",
    "                if s >= mid:\n",
    "                    s = 0\n",
    "                    p -= 1\n",
    "                if p==0:\n",
    "                    break\n",
    "            \n",
    "            if p == 0:\n",
    "                mini = mid\n",
    "            else:\n",
    "                maxi = mid\n",
    "            # print(mini, maxi)\n",
    "            \n",
    "        return mid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        :param sweetness:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def check(n):\n",
    "            cache1 = 0\n",
    "            cnt = 0\n",
    "            for i in sweetness:\n",
    "                cache1 += i\n",
    "                if cache1 >= n:\n",
    "                    cache1 = 0\n",
    "                    cnt += 1\n",
    "            return cnt > k\n",
    "\n",
    "        l,r = 0, 10**9+7\n",
    "\n",
    "        while l < r:\n",
    "            if l + 1 == r:\n",
    "                if check(r):\n",
    "                    return r\n",
    "                return l\n",
    "            mid = (l+r) //2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        def count(minval):\n",
    "            theSum = 0\n",
    "            count = 0\n",
    "\n",
    "            for each in sweetness:\n",
    "                if theSum + each >= minval:\n",
    "                    theSum = 0\n",
    "                    count += 1\n",
    "                else:\n",
    "                    theSum += each\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        # 筛选所有块中最小值的最大值\n",
    "        print(sum(sweetness))\n",
    "        temp_list = range(sum(sweetness), min(sweetness)-1, -1)\n",
    "        index = bisect_left(temp_list, k+1, key = count)\n",
    "        return temp_list[index]\n",
    "\n",
    "# class Solution:\n",
    "#     def maximizeSweetness(self, nums: List[int], k: int) -> int:\n",
    "#         def count(minimal):\n",
    "#             count,total=0,0\n",
    "#             for i in nums:\n",
    "#                 if i+total>=minimal:\n",
    "#                     count+=1\n",
    "#                     total=0\n",
    "#                 else:\n",
    "#                     total+=i\n",
    "#             return count\n",
    "#         index=bisect_left(range(sum(nums),min(nums)-1,-1), k+1, key=count)\n",
    "#         return sum(nums)-index"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
